package com.dxb.test.sort;

/**
 * 插入排序
 * 基本思想：
 * 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。
 */
public class InsertSort extends BaseSort {
    public InsertSort(int[] array) {
        super(array);
    }

    @Override
    public void sort() {
        for (int i = 1; i < length; i++) {
            int current = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > current) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = current;
        }

    }

    public static void main(String[] args) {
        int[] array = {38, 65, 97, 76, 13, 27, 49};
        InsertSort is = new InsertSort(array);
        is.run();
    }
}
